package main.leetcode.primary.from201to300;

/**
 * 208. 实现 Trie (前缀树)
 *
 * <p>实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
 *
 * <p>示例: Trie trie = new Trie(); <br>
 * trie.insert("apple"); <br>
 * trie.search("apple"); // 返回 true <br>
 * trie.search("app"); // 返回 false <br>
 * trie.startsWith("app"); // 返回 true <br>
 * trie.insert("app"); <br>
 * trie.search("app"); // 返回 true
 *
 * <p>说明: 你可以假设所有的输入都是由小写字母 a-z 构成的。 保证所有输入均为非空字符串。
 */
public class ex208 {
    public static void main(String[] args) {
        Trie root = new Trie();
        root.insert("apple");
        System.out.println(root.search("apple"));
        System.out.println(root.search("app"));
        System.out.println(root.startsWith("app"));
        root.insert("app");
        System.out.println(root.search("app"));
    }

    static class Trie {
        private Trie[] next;
        private boolean isEnd;
        /** Initialize your data structure here. */
        public Trie() {
            next = new Trie[26];
            isEnd = false;
        }

        /** Inserts a word into the trie. */
        public void insert(String word) {
            Trie cur = this;
            char[] chars = word.toCharArray();
            for (char aChar : chars) {
                int pos = aChar - 'a';
                if (cur.next[pos] == null) {
                    cur.next[pos] = new Trie();
                }
                cur = cur.next[pos];
            }
            cur.isEnd = true;
        }

        /** Returns if the word is in the trie. */
        public boolean search(String word) {
            char[] chars = word.toCharArray();
            Trie cur = this;
            for (char aChar : chars) {
                int pos = aChar - 'a';
                if (cur.next[pos] == null) {
                    return false;
                }
                cur = cur.next[pos];
            }
            return cur.isEnd;
        }

        /** Returns if there is any word in the trie that starts with the given prefix. */
        public boolean startsWith(String prefix) {
            char[] chars = prefix.toCharArray();
            Trie cur = this;
            for (char aChar : chars) {
                int pos = aChar - 'a';
                if (cur.next[pos] == null) {
                    return false;
                }
                cur = cur.next[pos];
            }
            return true;
        }
    }
}
